#include <stdio.h>
#include <limits>
#include "ListaAtri.h"
#include "ListaAresta.h"
#include "SolucaoGRASPCobertura.h"

#define MAX_CUSTO 10000000

SolucaoGRASPCobertura::SolucaoGRASPCobertura(){
     	this->saida  = new char[Solucao::F + 1];
     	this->solucao = new bool[Solucao::F];
	this->c = new int[Solucao::V];
	this->avaliacao = 0;
}

SolucaoGRASPCobertura::SolucaoGRASPCobertura(SolucaoGRASPCobertura *sol){
	this->saida  = new char[Solucao::F+1];
	this->solucao = new bool[Solucao::F];
	this->c = new int[Solucao::V];

	this->avaliacao = sol->avaliacao;
	
	memcpy(this->solucao, sol->solucao, Solucao::F * sizeof(bool));
	memcpy(this->c, sol->c, Solucao::V * sizeof(int));
}

void SolucaoGRASPCobertura::init(){
	for(int i = 0; i < Solucao::V; i++)
		this->solucao[i] = false;
	
	for(int i = 0; i < Solucao::F; i++)
		c[i] = -1;
}

int SolucaoGRASPCobertura::f()
{
	this->avaliacao = 0;
	for(int v=0; v<Solucao::V; ++v)
		this->c[v] = -1;


        int actives = 0;

	for(int f=0; f<Solucao::F; ++f){
		if(this->solucao[f]){
                    actives++;
    			list<int>::iterator it = (*NV)[f].begin();
    			for(; it != (*NV)[f].end(); ++it){
				int v = *it;
				//if((Solucao::type[v] == FACILITY) || (Solucao::type[v] == FACILITY_ACTIVE)){
				//	continue;
				//}
				//printf("Cli: %d Fac: %d Dist: %f\n", v, f, linkClient[v][f]);
				if(this->c[v] == -1){
					this->c[v] = f;
					this->avaliacao += this->demanda[v];
				}else{
					if(Solucao::linkClient[v][f] < Solucao::linkClient[v][this->c[v]])
						this->c[v] = f;
				}
			}
		}
	}

        printf("FACILITADORES ATIVOS2: %d\n", actives);
	return this->avaliacao;
}

//Dispersão dos facilitadores no espa�o do seu cluster.
double SolucaoGRASPCobertura::g(int f){
    double demanda = 0;
    list<int>::iterator it = (*NV)[f].begin();
    for(; it != (*NV)[f].end(); ++it){
		int v = *it;
		//if((Solucao::type[v] == FACILITY) || (Solucao::type[v] == FACILITY_ACTIVE))
		//	continue;
		//if(this->c[v] == -1){
		demanda += this->demanda[v];
		//}
    }
    return demanda;
}

#include "Lista.h"

void SolucaoGRASPCobertura::setElemento(int f){
	this->solucao[f] = true;
    	list<int>::iterator it = (*NV)[f].begin();
    	for(; it != (*NV)[f].end(); ++it){
		int v = *it;
		if(this->c[v] == -1){
			this->c[v] = f;
			this->avaliacao += this->demanda[v];
			//printf("F: %d V: %d DEM: %d\n", f, v, this->demanda[v]);
		}else{
			if(Solucao::linkClient[v][f] < Solucao::linkClient[v][this->c[v]])
				this->c[v] = f;
		}
	}
}

//Calcula a avalia��o do vizinho sem gerar o movimento na solu��o.
inline int SolucaoGRASPCobertura::getVizinhoAval(int f){
	int demanda = this->avaliacao;
	if(this->solucao[f] != true){//ADD
    		list<int>::iterator it = (*NV)[f].begin();
    		for(; it != (*NV)[f].end(); ++it){
			int v = *it;
			//if((Solucao::type[v] == FACILITY) || (Solucao::type[v] == FACILITY_ACTIVE))
			//	continue;
			if(this->c[v] == -1)
				demanda += this->demanda[v];
		}
	}else{//DROP
    	    list<int>::iterator it = (*NV)[f].begin();
    	    for(; it != (*NV)[f].end(); ++it){
		int v = *it;
		if(this->c[v] == f){
			bool find = false;
    	    		list<int>::iterator itf = (*NF)[v].begin();
    	    		for(; itf != (*NF)[v].end(); ++itf){
				int fa = *itf;
				if((this->solucao[fa]) && (fa != f)){
					find = true;
					break;
				}
			}
			if(!find){
				demanda -= this->demanda[v];
			}
		}
	    }		
	}
	return demanda;  
}

/**
  * Troca o estado(ativo/inativo) de um nao, realocando os clientes a ele atribuído. 
  * O valor de avaliacao da solução é atualizado. 
  */
void SolucaoGRASPCobertura::getVizinho2(int f){
	if(this->solucao[f] == true)
		this->solucao[f] = false;
	else
		this->solucao[f] = true;

	if(this->solucao[f] == true){
    		list<int>::iterator it = (*NV)[f].begin();
    		for(; it != (*NV)[f].end(); ++it){
			int v = *it;
			//if((Solucao::type[v] == FACILITY) || (Solucao::type[v] == FACILITY_ACTIVE))
			//	continue;
			if(this->c[v] == -1){
				this->c[v] = f;
				this->avaliacao += this->demanda[v];
			}else{
				if(Solucao::linkClient[v][f] < Solucao::linkClient[v][this->c[v]])
					this->c[v] = f;
			}
		}	
	}else{
    		list<int>::iterator it = (*NV)[f].begin();
    		for(; it != (*NV)[f].end(); ++it){
			int v = *it;
			if(this->c[v] == f){
				bool find = false;
				double maxDist = Solucao::D;
    	    			list<int>::iterator itf = (*NF)[v].begin();
    	    			for(; itf != (*NF)[v].end(); ++itf){
					int fa = *itf;
					if(this->solucao[fa]){
						if(Solucao::linkClient[v][fa] <= maxDist){
							this->c[v] = fa;
							maxDist = Solucao::linkClient[v][fa];
						}
						find = true;
					}
				}
				if(!find){
					this->avaliacao -= this->demanda[v];
					this->c[v] = -1;
				}
			}
		}
	}
}

SolucaoGRASPCobertura *SolucaoGRASPCobertura::getVizinho(int f){
	SolucaoGRASPCobertura *s = new SolucaoGRASPCobertura(this);
	if(s->solucao[f] == true)
		s->solucao[f] = false;
	else
		s->solucao[f] = true;

	if(s->solucao[f] == true){
    		list<int>::iterator it = (*NV)[f].begin();
    		for(; it != (*NV)[f].end(); ++it){
			int v = *it;
			//if((Solucao::type[v] == FACILITY) || (Solucao::type[v] == FACILITY_ACTIVE))
			//	continue;
			if(s->c[v] == -1){
				s->c[v] = f;
				s->avaliacao += s->demanda[v];
			}else{
				if(Solucao::linkClient[v][f] < Solucao::linkClient[v][s->c[v]])
					s->c[v] = f;
			}
		}
	}else{
    		list<int>::iterator it = (*NV)[f].begin();
    		for(; it != (*NV)[f].end(); ++it){
			int v = *it;
			if(s->c[v] == f){
				bool find = false;
    	    			list<int>::iterator itf = (*NF)[v].begin();
    	    			for(; itf != (*NF)[v].end(); ++itf){
					int fa = *itf;
					if(s->solucao[fa]){
						if(Solucao::linkClient[v][fa] < Solucao::linkClient[v][s->c[v]])
							s->c[v] = fa;
						find = true;
					}
				}
				if(!find){
					s->avaliacao -= s->demanda[v];
					s->c[v] = -1;
				}
			}
		}
	}  
	return s;
}


SolucaoGRASPCobertura *SolucaoGRASPCobertura::getSWAP(int i, int j){
	//if((Solucao::type[i] == Solucao::CLIENT) || (Solucao::type[j] == Solucao::FACILITY_ACTIVE))
	//	return NULL;
	SolucaoGRASPCobertura *s = new SolucaoGRASPCobertura(this); 
	s->getVizinho2(i); 
	s->getVizinho2(j); 
	return s;
}

//Avalia primeiro e realiza o movimento no melhor
//Troca os facilitadores no mesmo cluster.
SolucaoGRASPCobertura *SolucaoGRASPCobertura::getVizinhosSWAP(){
        //ListaSolucao *vizinhos = new ListaSolucao();
	SolucaoGRASPCobertura *solSwap = NULL;//new SolucaoGRASPCobertura(this);
	NoClu *cluster = Solucao::clusters.inicio;
	while(cluster){
        if(cluster->visitado1){
             cluster = cluster->proximo;
             continue;
        }
        NoLista *aux = cluster->lista->inicio;
        while(aux){
            if(this->solucao[aux->elemento] == false){ 
		//	|| (Solucao::type[aux->elemento] == Solucao::FACILITY_ACTIVE)){
                aux = aux->proximo;
		continue;
            }
            SolucaoGRASPCobertura *sol = new SolucaoGRASPCobertura(this);
            double bestAval = sol->avaliacao;
            int pos = -1;
            sol->getVizinho2(aux->elemento);
	    //printf("DROP F: %d\n", sol->avaliacao);
            NoLista *a = cluster->lista->inicio;
	    while(a){
                if(sol->solucao[a->elemento] == true){ 
		//	|| (Solucao::type[aux->elemento] == Solucao::CLIENT)){
                    a = a->proximo;
		    continue;
                }
                //double aval = sol->getVizinhoAval(a->elemento);
		int f = a->elemento;
		double aval = sol->avaliacao;
        	if(sol->solucao[f] != true){//ADD
                	list<int>::iterator it = (*NV)[f].begin();
                	for(; it != (*NV)[f].end(); ++it){
                        	int v = *it;
                        	//if((Solucao::type[v] == FACILITY) || (Solucao::type[v] == FACILITY_ACTIVE))
                        	//      continue;
                        	if(this->c[v] == -1)
                                	aval += this->demanda[v];
                	}
        	}else{//DROP
            		list<int>::iterator it = (*NV)[f].begin();
            		for(; it != (*NV)[f].end(); ++it){
               			int v = *it;
                		if(this->c[v] == f){
                        		bool find = false;
                        		list<int>::iterator itf = (*NF)[v].begin();
                        		for(; itf != (*NF)[v].end(); ++itf){
                                		int fa = *itf;
                                		if((this->solucao[fa]) && (fa != f)){
                                        		find = true;
                                        		break;
                                		}
                        		}
                        		if(!find){
                                		aval -= this->demanda[v];
                        		}
                		}
            		}
		}
        
		//printf("ADD F: %lf\n", aval);
                if(aval > bestAval){
                    bestAval = aval;
                    pos = a->elemento;
                }
                a = a->proximo;
           }
           if(pos == -1){
                aux = aux->proximo;
                delete sol;
                continue;
           }
           sol->getVizinho2(pos);
	       if(solSwap == NULL){
	            solSwap = sol;
           }else{
                if(sol->avaliacao > solSwap->avaliacao){
                    delete solSwap;
		    solSwap = sol;
                    return solSwap; //Retorna a primeira melhoria
                }else
                    delete sol;
	   }
			aux = aux->proximo;
        }
	cluster->visitado1 = true;
        cluster = cluster->proximo;
	}
	
    cluster = Solucao::clusters.inicio;
	while(cluster){
         cluster->visitado1 = false; 
         cluster = cluster->proximo;
    }
    if(solSwap == NULL)
         return new SolucaoGRASPCobertura(this);
    return solSwap;
}

SolucaoGRASPCobertura *SolucaoGRASPCobertura::getVizinhosSWAPCluster(){
    //ListaSolucao *vizinhos = new ListaSolucao();
	SolucaoGRASPCobertura *solSwap = NULL;//new SolucaoGRASPCobertura(this);
	
    NoClu *cluster = Solucao::clusters.final;
    for(int c=0; c<Solucao::clusters.count; ++c){
		if(cluster->visitado2){
             cluster = cluster->anterior;
             continue;
        }
        
        //if(cluster->tamanho > 11)
        //     break;
        NoLista *aux = cluster->lista->inicio;
        while(aux){
            if(this->solucao[aux->elemento] == false){ 
		//			|| (Solucao::type[aux->elemento] == Solucao::FACILITY_ACTIVE)){
                aux = aux->proximo;                            
				continue;
            }
            SolucaoGRASPCobertura *sol = new SolucaoGRASPCobertura(this);
            double bestAval = sol->avaliacao;
            int pos = -1;
            sol->getVizinho2(aux->elemento);
            
            NoClu *c = Solucao::clusters.inicio;
            while(c){
                 if(c == cluster){// N�o trocar no mesmo cluster
                      c = c->proximo;
                      continue;
                 }
                 NoLista *a = c->lista->inicio;
                 while(a){
                    if(this->solucao[a->elemento] == true){
			//	&& (Solucao::type[aux->elemento] != Solucao::CLIENT)){
                         double aval = sol->getVizinhoAval(a->elemento);
                         if(aval > bestAval){
                                 bestAval = aval;
                                 pos = a->elemento;
                         }
                    }
                    a = a->proximo;
                 }
                 c = c->proximo;
            }
            if(pos == -1){
                  aux = aux->proximo;
                  delete sol;
                  continue;
            }
            sol->getVizinho2(pos);
	        //puts("H6.2");
	        if(solSwap == NULL){
	                  solSwap = sol;
            }else{
                if(sol->avaliacao > solSwap->avaliacao){
                      delete solSwap;
				      solSwap = sol;
				      //puts("H6.3");
                      return solSwap; //Retorna a primeira melhoria
                }else
                     delete sol;
                  //puts("H6.4");
             }

			aux = aux->proximo;
		}
		cluster->visitado2 = true;
		cluster = cluster->anterior;
	}
	
	cluster = Solucao::clusters.inicio;
	while(cluster){
         cluster->visitado2 = false; 
         cluster = cluster->proximo;
    }
	
	if(solSwap == NULL)
         return new SolucaoGRASPCobertura(this);
    return solSwap;
}
